package Leetcode.Stack;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @Author: kirito
 * @Date: 2024/4/19 12:25
 * @Description:
 * 柱状图中最大的矩形
 * 困难
 * 相关标签
 * 相关企业
 * 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
 *
 * 求在该柱状图中，能够勾勒出来的矩形的最大面积。
 *
 *
 *
 * 示例 1:
 *
 *
 *
 * 输入：heights = [2,1,5,6,2,3]
 * 输出：10
 * 解释：最大的矩形为图中红色区域，面积为 10
 * 示例 2：
 *
 *
 *
 * 输入： heights = [2,4]
 * 输出： 4
 *
 *
 * 提示：
 *
 * 1 <= heights.length <=105
 * 0 <= heights[i] <= 104
 */

public class largestRectangleArea {
    public static void main(String[] args) {
        int[] arr = {2, 1, 5, 6, 2, 3};
        System.out.println(largestRectangleArea(arr));

    }
    /**
     * 面积最大，那么最大矩形的高度一定是heights中的数，如果不是就可以增加高度直到触及柱子的顶部
     * 假设h是heights[i]的高度  那么矩形宽度是多少
     *      在i左侧小于h的最近元素的下标left
     *      在i右侧小于h的最近元素的下标right
     * @param heights
     * @return
     */
    public static int largestRectangleArea(int[] heights) {
        int len = heights.length;
        int[] left = new int[len];
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < len; i++) {
            int h = heights[i];
            while (!stack.isEmpty() && h <= heights[stack.peek()]) {
                stack.pop();
            }
            //此时找到了比h小的元素下标left
            left[i] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(i);
        }

        //同理求右边界
        int[] right = new int[len];
        stack.clear();
        for (int i = len - 1; i >= 0; i--) {
            int h = heights[i];
            while (!stack.isEmpty() && h <=  heights[stack.peek()]) {
                stack.pop();
            }
            right[i] = stack.isEmpty() ? len : stack.peek();
            stack.push(i);
        }

        int ans = 0;
        for (int i = 0; i < len; i++) {
            int h = heights[i];
            ans = Math.max(ans, h * (right[i] - left[i] - 1));
        }
        return ans;
    }

}
